﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.LinkedList
{
  
    //Definition for singly-linked list.
    public class LinkedNode
    {
        public int val;
        public LinkedNode next;
        public LinkedNode(int x)
        {
            val = x;
            next = null;
        }
    }

    public class _141
    {
        //我们还可以考虑快慢指针的解法，如果链表中有环，
        //意味着不断访问next指针，最后会陷入一个循环当中。
        //我们可以想象成在一个环形跑道上，跑的快的人和跑的慢的人同时出发，
        //随着时间的推移，跑的快的人一定会追上跑的慢的人。
        //也就是说，快满指针相遇即判定链表有环。
        //如果跑的快的人先到达了终点，说明不存在循环跑道，即链表无环。
        public bool HasCycle(LinkedNode head)
        {
            if (head == null || head.next == null)
            {
                return false;
            }
            LinkedNode slow = head;
            LinkedNode fast = head.next;
            while (slow != fast)
            {
                if (fast == null || fast.next == null)
                {
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;

        }
        /// <summary>
        /// 142给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
        ///为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 
        /// 如果 pos 是 -1，则在该链表中没有环。
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public LinkedNode detectCycle(LinkedNode head)
        {
            LinkedNode fast = head, slow = head;
            while (true)
            {
                if (fast == null || fast.next == null) return null;
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) break;
            }
            fast = head;
            while (slow != fast)
            {
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
        //     7<-6<- 5
        //      |     ^
        //      |     |
        //0->1->2->3->4
        //[-----]
        //        a
        //简单说一下，如上图所示
        //我们设置快慢两个指针，fast, slow fast一次前进两步，slow一次前进一步，
        //设a为第一个节点到入环节点的距离。 a=[0->2]
        //        设b为入环口到相遇点的距离。b=[2->6]
        //        设c为相遇点到入环口的距离。c=[6->2]
        //        当fast，和slow相遇的时候，fast经过的节点是slow的两倍，设slow经过的节点数为S
        //        根据上面的设置 可知 S = a + b,2S=a+b+c+b，可知 a = c, 此时让slow回到第一个节点，
        //fast处于第一次相遇的节点，此时slow从第一个节点出发，因为a=c，所以fast，和slow会在入环口第二次相遇，得到要求的节点。
    }

}
